//
// Created by CodeZijun on 2022/12/9.
//

#ifndef DATASTRUCTURES_GRAPH_H
#define DATASTRUCTURES_GRAPH_H
#include <iostream>
#include <vector>
#include <utility>
#include <unordered_map>
using namespace std;
const int N = 50;
#define INF 0x3f3f3f3f

//邻接矩阵
struct adjMatrix{
    unordered_map<int,int> vertex;
    int matrix[N][N];
    int cnt = 0;
    adjMatrix(){
        for(int i = 0; i < N ; i++)
            for(int j = 0; j < N ; j++)
                if(i == j)
                    matrix[i][j] = 0;
                else
                    matrix[i][j] = INF;
    }
};

//邻接表
struct edge{
    int adjVertex;
    int weight;
    edge* next;
    edge(){
        adjVertex = 0;
        weight = 0;
        next = nullptr;
    }
};
struct adjList{
    vector<pair<int,edge*>> vertex;
    int find(int x){
        for(int i = 0; i < vertex.size(); i++){
            if(vertex[i].first == x)
                return i;
        }
        return -1;
    }
    void insertVertex(int data){
        if(find(data) != -1)
            return;
        pair<int,edge*> p;
        p.first = data;
        p.second = nullptr;
        vertex.push_back(p);
    }
    void insertArc(int i, int j, int w){
        edge* p = new edge;
        p->weight = w;
        p->adjVertex = find(j);
        p->next = vertex[find(i)].second;
        vertex[find(i)].second = p;
    }
    void printAdjVertex(int i){
        edge* p = vertex[i].second;
        cout<<vertex[i].first<<"的邻接点:"<<endl;
        while(p){
            cout<<"点:"<<vertex[p->adjVertex].first<<"权:"<<p->weight<<endl;
            p = p->next;
        }
    }
};

//十字链表
struct arc{
    int weight;
    int tailVertex;
    int headVertex;
    arc* inNext;
    arc* outNext;
    arc(){
        weight = 0;
        tailVertex = 0;
        headVertex = 0;
        inNext = nullptr;
        outNext = nullptr;
    }
};
struct ver{
    int data;
    arc* firstIn;
    arc* firstOut;
    ver(){
        data = 0;
        firstIn = nullptr;
        firstOut = nullptr;
    }
    ver(int n){
        data = n;
        firstIn = nullptr;
        firstOut = nullptr;
    }
};
struct ortList{
    vector<ver*> vertex;
    int find(int x){
        for(int i=0; i<vertex.size();i++)
            if(vertex[i]->data == x)
                return i;
        return -1;
    }
    void insertVertex(int n){
        if(find(n) != -1)
            return;
        ver* p = new ver(n);
        vertex.push_back(p);
    }
    void insertArc(int i, int j, int w){
        arc* p = new arc;
        p->weight = w;
        p->tailVertex = find(i);
        p->headVertex = find(j);
        p->outNext = vertex[p->tailVertex]->firstOut;
        vertex[p->tailVertex]->firstOut = p;
        p->inNext = vertex[p->headVertex]->firstIn;
        vertex[p->headVertex]->firstIn = p;
    }
    void printInDegree(){
        for(int i=0; i<vertex.size(); i++){
            cout<<vertex[i]->data<<"的入度为:";
            int cnt=0;
            arc* p = vertex[i]->firstIn;
            while(p){
                cnt++;
                p = p->inNext;
            }
            cout<<cnt<<endl;
        }
    }
    void printOutDegree(){
        for(int i=0; i<vertex.size(); i++){
            cout<<vertex[i]->data<<"的出度为:";
            int cnt = 0;
            arc* p =vertex[i]->firstOut;
            while(p){
                cnt++;
                p = p->outNext;
            }
            cout<<cnt<<endl;
        }
    }
};

//邻接多重表
struct mArc{
    int iVer;
    int jVer;
    int weight;
    mArc* iLink;
    mArc* jLink;
    mArc(){
        iVer = 0;
        jVer = 0;
        iLink = nullptr;
        jLink = nullptr;
        weight = 0;
    }
    mArc(int i, int j, int w){
        iVer = i;
        jVer = j;
        iLink = nullptr;
        jLink = nullptr;
        weight = w;
    }
};
struct mAdjList{
    vector<pair<int,mArc*>> vertex;
    int find(int x){
        for(int i=0; i<vertex.size();i++){
            if(x == vertex[i].first)
                return i;
        }
        return -1;
    }
    void insertVertex(int n){
        if(find(n) != -1)
            return ;
        pair<int,mArc*> p;
        p.first = n;
        p.second = nullptr;
        vertex.push_back(p);
    }
    void insertArc(int i, int j, int w){
        mArc* p = new mArc(find(i),find(j),w);
        p->iLink = vertex[p->iVer].second;
        vertex[p->iVer].second = p;
        p->jLink = vertex[p->jVer].second;
        vertex[p->jVer].second = p;
    }
    void printAdjList(){
        for(int i=0;i<vertex.size();i++){
            cout<<vertex[i].first<<"的邻接点"<<endl;
            mArc* p = vertex[i].second;
            while(p){
                if(p->iVer == i){
                    cout<<"点"<<vertex[p->jVer].first<<"权"<<p->weight<<endl;
                    p = p->iLink;
                }
                else if(p->jVer == i){
                    cout<<"点"<<vertex[p->iVer].first<<"权"<<p->weight<<endl;
                    p = p->jLink;
                }
            }
        }
    }
};

class Graph {
public:
    adjMatrix* adjMat;
    adjList* adjL;
    ortList* ortL;
    mAdjList* mAdjL;
    void udCreateGraphAdjMatrix();
    void dCreateGraphAdjMatrix();
    void createGraphAdjList();
    void createOrtList();
    void createMAdjList();
    void printAdjMatrix();
    Graph(){
        adjMat = new adjMatrix;
        adjL = new adjList;
        ortL = new ortList;
        mAdjL = new mAdjList;
    }
};


#endif //DATASTRUCTURES_GRAPH_H
